package linked;

public class Ex160 {
    public class Solution {
        public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) return null;
            
            ListNode a = headA, b = headB;
            while (a.next != null && b.next != null) {
                a = a.next;
                b = b.next;
            }

            int count = 0;
            //记录是否发生了交换
            boolean flag = false;

            //使得a永远是较长的那个链表
            if (a.next == null) {
                ListNode temp = b;
                b = a;
                a = temp;
                flag = true;
            }

            while (a.next != null) {
                a = a.next;
                count++; //a，b之间的长度差
            }

            if (a != b) return null; //两者的末尾节点不相同，说明两者不相交

            if (flag) {
                //发生了交换，说明B链表比较长，还是让A长
                ListNode temp = headA;
                headA = headB;
                headB = temp;
            }

            //从头遍历，让a先走count步
            a = headA;
            b = headB;
            while (count != 0) {
                a = a.next;
                count--;
            }

            while (a != null && b != null) {
                if (a == b) return a;
                a = a.next;
                b = b.next;
            }

            return null;
        }

        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            ListNode a = headA, b = headB;
            while (a != b) {
                a = a == null ? headB : a.next;
                b = b == null ? headA : b.next;
            }
            return a;
        }
    } 
}
